package demo01;

import java.util.Stack;

public class HanoiTower {

    /**
     * 递归实现汉诺塔算法
     *
     * @param n 盘子的数量
     * @param from 初始柱子
     * @param to 目标柱子
     * @param aux 辅助柱子
     */
    public void solveHanoiRecursive(int n, String from, String to, String aux) {
        // 如果只有一个盘子，直接从from移动到to
        if (n == 1) {
            System.out.println("移动盘子 1: " + from + " -> " + to);
            return;
        }

        // 1. 将n-1个盘子从from移动到aux（借助于to）
        solveHanoiRecursive(n - 1, from, aux, to);

        // 2. 将第n个盘子（最大的盘子）从from移动到to
        System.out.println("移动盘子 " + n + ": " + from + " -> " + to);

        // 3. 将n-1个盘子从aux移动到to（借助于from）
        solveHanoiRecursive(n - 1, aux, to, from);
    }
    
    /**
     * 非递归实现汉诺塔算法
     *
     * @param n 盘子的数量
     * @param from 初始柱子
     * @param to 目标柱子
     * @param aux 辅助柱子
     */
    public void solveHanoiIterative(int n, String from, String to, String aux) {
        // 定义栈来存储移动过程中的状态，每个元素是一个数组，包含盘子数量和三个柱子
        Stack<Object[]> stack = new Stack<>();
        stack.push(new Object[]{n, from, to, aux});

        while (!stack.isEmpty()) {
            Object[] current = stack.pop();
            int currentN = (int) current[0];
            String currentFrom = (String) current[1];
            String currentTo = (String) current[2];
            String currentAux = (String) current[3];

            if (currentN == 1) {
                System.out.println("移动盘子 1: " + currentFrom + " -> " + currentTo);
            } else {
                // 模拟递归的步骤，逆序入栈
                
                // 3. 将n-1个盘子从aux移动到to（借助于from）
                stack.push(new Object[]{currentN - 1, currentAux, currentTo, currentFrom});
                
                // 2. 将第n个盘子从from移动到to
                // 这一步是打印输出，不需要入栈
                stack.push(new Object[]{1, currentFrom, currentTo, "dummy"}); // 用1个盘子的特殊情况来表示打印操作
                
                // 1. 将n-1个盘子从from移动到aux（借助于to）
                stack.push(new Object[]{currentN - 1, currentFrom, currentAux, currentTo});
            }
        }
    }

    public static void main(String[] args) {
        HanoiTower hanoi = new HanoiTower();
        int n = 10; // 盘子数量

        System.out.println("--- 递归实现汉诺塔, 盘子数量: " + n + " ---");
        hanoi.solveHanoiRecursive(n, "A", "C", "B");

        System.out.println("\n--- 非递归实现汉诺塔, 盘子数量: " + n + " ---");
        hanoi.solveHanoiIterative(n, "A", "C", "B");
    }
}